Mobile ad-hoc networks (“MANETs”) will likely be of growing importance for a variety of applications, such as computer-based collaborative networks and military communications. Each unit, or node, in a typical MANET may initiate, receive, and forward communications. Since the units are mobile, a functioning MANET may need to accommodate variations in a communication pathway between any two units.
A network of citizens-band radios (commonly called CB radio) is perhaps the earliest and best known example of a radio-based MANET. A CB radio, i.e., a node in a MANET made up of CB radios, has a broadcast range limited to approximately 15 miles. Three or more mobile units—located, for example, in trucks or automobiles—can participate in the exchange of communications between two units when the two units are too distant from each other for direct radio contact. In this example, those individuals controlling the additional unit(s) may relay communications between the two units that are outside of each others' direct radio contact. Such a sequence of nodes relaying messages for a pair of units forms a communication pathway, or a route, between the pair. The decisions leading to choosing a sequence of units to form a communication pathway is called routing. A communication can include, for example, a message and the identity of the intended recipient of the message.
All units in a MANET may be in constant motion. Thus, the neighboring nodes that are available for direct communication may change over time. At any given moment of time, the collective knowledge of which units are in the neighborhood of each unit in such a network is called the network's configuration. As a result of the configuration variation, a communication pathway between a pair of communicating units may vary with time.
A communication pathway can change rapidly because the quality of radio transmissions between any two adjacent units in a communications pathway may be affected by variations in, for example, the radio propagation environment and movement of the units. These changes may occur during the transmission of a single packet of information, and hence may cause the transmission of such a single packet be disrupted.
For example, in radio-based networks, the radio signals may exhibit signal strength variations. The relative movements of a transmitting node, a receiving node, and/or other structures acting as reflectors or obstructions may introduce Doppler effect-related signal distortions, may cause multi-path destructive interference, or may completely block a signal. Such factors cause pathway link characteristics to vary more dramatically and over a much larger range than encountered in traditional fixed-link networks.
As in any communications network, proper functioning of a MANET requires an effective message routing protocol, which itself may require maintenance of knowledge of variations in the network's configuration. Such information, however, typically must be disseminated through the MANET itself. Hence, the amount of networking resources (e.g., communications bandwidth and mobile unit battery power) that a routing protocol requires to function properly must also be considered in evaluating its effectiveness.
A number of routing methods have been proposed for use in MANETs. These largely employ broadcast routing of communications, where a message packet contains routing information to enable forwarding of the packet to the destination unit. Under this protocol, units forward messages using either a connectionless or connection-oriented approach. Both approaches require that each mobile unit participate in a background effort to maintain up-to-date information on network configuration variations over time, and a routing pathway is determined prior to transmission of a communication along the pathway.
Some traditional networks include mobile nodes and a fixed infrastructure to support message-forwarding instructions. Such networks create location registries to maintain a database of mobile node locations that can be shared with the nodes. A pure MANET, however, has no access to a fixed infrastructure that includes fixed nodes to provide such services. An attempt to use mobile nodes to support a location registry service can be problematic; for example, to communicate with a mobile node, a node may need to access the location registry, however, the location registry is itself carried by a mobile node.
Some alternatives to implementation of a location registry are based on a probe-once-and-then-reuse-many-times approach, such as the Ad-Hoc On-Demand Distance Vector Routing (AODV) approach. The probe-once-and-then-reuse-many-times approach, while useful in many cases, is not appropriate when the nodal mobility renders the probed route useless very quickly, i.e., when route persistence is brief. Because a route typically includes a series of links, the persistence of the route depends on the persistence of every link in the route. Hence, the persistence of a route may be brief even for moderate amounts of node movement when a route includes more than a few links.